COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	 The following is an input independent average linear time algorithm for
C00006 00003	(defun findhash (l)
C00009 00004	 HASH2 is a hash function for two fixnums.    HASH2MAC is a macro for same.
C00010 ENDMK
C⊗;
;;; The following is an input independent average linear time algorithm for
;;; storage and retrieval on keys.   The algorithm makes a random choice of
;;; hash functions from a suitable class of hash functions.   Given any
;;; sequence of inputs, the expected time (averaging over all functions in
;;; in the class) to store and retrieve elements is linear in the length of
;;; the sequence.   The number of references to the data base required by
;;; the algorithm for any input is extremely close to the theoretical minimum
;;; for any possible hash function with randomly distributed inputs.   
;;; (Reference: Carter and Wegman 1977)

;;; Note that the performance of the algorithm is independent of the
;;; distribution of the input.    Thus it is not necessary for a user of the
;;; algorithm to take into account any clustering tendencies of the data --
;;; that they are all addresses or integers in some small range, or whatever.

;;; To initialize the function, call (definehash n) where n is the desired
;;; size of the hash table; the table is called hashtable.    (inithash)
;;; reinitializes the hash table and randomly chooses a new hashing function.
;;; (hash l) takes a list l of fixnums and returns a fixnum in the range
;;; of the size of the hash table.   (hash ...) is coded in LAP.

;;; There is also a function findhash which you might find useful.  (findhash l)
;;; searches through (hashtable (hash l)), a list it maintains.  If it finds an
;;; an entry (using equal) of the form (l . <anything>), it returns <anything>.
;;; Otherwise it returns a new dotted pair (cons l nil), which it has added to
;;; the list and which you can rplacd to insert <anything>.

(declare (special hashp hasha hashb) (fixnum hashp hashb)
	 (array* (notype hashtable 1)))

(defun definehash (n) (setq hashp n) (array hashtable t hashp) (inithash))

(defun inithash () 
       (setq hashb (1- hashp))
       (setq hasha nil)
       (do i 0. (1+ i) (= i 30.) (setq hasha (cons (1+ (random hashb)) hasha)))
       (setq hashb (1+ (random hashb)))
       (fillarray 'hashtable '(nil)))

(lap hash subr)
(args hash (nil . 1))
(move b (special hasha))
(setz 6)
hashloop
(jumpe a hashend)
(hlrz 7 0 a)
(move 7 0 7)
(hlrz 10 0 b)
(move 10 0 10)
(imul 7 10)
(add 6 7)
(hrrz a 0 a)
(hrrz b 0 b)
(jrst 0 hashloop)
hashend
(add 6 @ (special hashb))
(idiv 6 @ (special hashp))
(jsp t fxcons)
(popj p)
nil
(defun findhash (l)
       (prog (bucket hashl)
	     (setq hashl (hash l))
	     (setq bucket (hashtable hashl))
	     lab
	     (cond ((null bucket) 
		    (setq l (cons l nil))
		    (store (hashtable hashl) (cons l (hashtable hashl)))
		    (return l))
		   ((equal l (caar bucket)) (return (cdar bucket)))
		   (t (setq bucket (cdr bucket))
		      (go lab)))))

;;; The following are for testing and analyzing the hash function.

(declare (special hashhit))

(defun printhash ()
       (do i 0 (1+ i) (= i hashp)
	   (cond ((null (hashtable i)))
		 (t (print i) 
		    (princ (ascii 9.))
		    (princ (hashtable i))))))

(defun testhash (n listsize numsize)
       (prog (x l)
	     (inithash)
	     (setq hashhit 0)
	     (array testarray fixnum 10.)
	     (do i 0 (1+ i) (= i n)
		 (setq l nil)
		 (setq x (1+ (random listsize)))
		 (do j 0 (1+ j) (= j x)
		     (setq l (cons (random numsize) l)))
		 (or (findhash l) (setq hashhit (1+ hashhit))))
	     (terpri)
	     (do i 0 (1+ i) (= i hashp)
		 (setq x (length (hashtable i)))
		 (store (testarray x) (1+ (testarray x))))
	     (setq l (listarray 'testarray))
	     (setq x 0)
	     (do i 1 (1+ i) (= i 10.)
		 (setq x (+ x (* i i (testarray i)))))
	     (return (list hashhit x l (//$ (float x) (float n)))))))
;;; HASH2 is a hash function for two fixnums.    HASH2MAC is a macro for same.

(lap hash2 subr)
(args hash2 (nil . 2))
(move t 0 a)
(move tt 0 b)
(imul t @ (special hasha))
(imul tt @ (special hashb))
(add t tt)
(add t @ (special hashc))
(idiv t @ (special hashp))	;remainder in tt
(jsp t fxcons)
(popj p)
nil

(defsmac hash (x y) (\ (+ (* x hasha) (* y hashb) hashc) hashp))